A stream comprises a succession of data packets, such as IP (Internet Protocol) datagrams. It is identified by a set of attributes which are present in the header of each of the packets which it comprises. By way of example, these attributes comprise a source IP address, a destination IP address, a source port, a destination port, a protocol identification, a stream identifier (“flow label”), etc. Thus, all of the packets having the same attribute values constitute a stream.
A stream is considered to be in progress at a given instant if the time which has elapsed since its last packet was observed is below a certain threshold TO, for example in the order of a few seconds.
Packet organization mechanisms which make use of the stream concept are known. They aim to establish an order in the delivery of the packets at the output of a router, for example. In particular, there is abundant literature on fair sharing (“Fair Queuing”) algorithms. These algorithms ensure a certain level of fairness between the streams when the packets are delivered. Among them, cited illustrations will be DRR (Deficit Round Robin), described by Shreedar and Varghese in “Efficient fair queuing using Deficit Round Robin”, IEEE/ACM Transactions on Networking, Volume: 4, Issue: 3, June 1996, Pages: 375-385, and SFQ (Start-time Fair Queueing), described by Goyal, Vin and Cheng in “Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks”. IEEE/ACM ToN, Vol. 5, No 5, October 1997. DRR is a reduced-complexity organization mechanism based on cyclic processing of the streams in line with a round robin principle. A queue is associated with each stream. The stream i is authorized to send at most one fixed quantum Q_i of bytes per cycle. It thus obtains a flow rate proportional to the value of its quantum Q_i. This mechanism allows a reasonable degree of fairness to be obtained by virtue of a deficit counter being kept which compensates for the possible difference in size between the packets from the different streams. The complexity is in the order O(1), that is to say that it is independent of the number of streams in progress.
SFQ is a mechanism which is part of the fair sharing algorithm class sometimes called “self-clocked”. The organization of the packets to be delivered is defined by a stamp attributed to each packet. The stream i is associated with a flow rate parameter R_i which determines the connection between the stamps for the packets in this stream.
The streams, in a packet network, are transitory in nature. The number of streams in progress at each instant is a variable which can reach a value of several tens of thousands over a high-capacity link (of 2.5 Gbps or more, for example). However, the number of streams which need to be known at each instant by the organization mechanism is considerably lower. Indeed, the delivery scheduler for the packets which is set up by the organization mechanism relates only to streams, called active streams, which have at least one packet queuing for the purpose of delivering it at the instant in question or, possibly, which have had one in the very recent past. This makes it possible to implement the fair sharing organization even for very high link flow rates, because the number of active streams is independent of the flow rate of the link and is limited to a few hundred, for example.
In fact, at each instant, the traffic can be broken down into two types of streams: constrained or “bottlenecked” streams, subsequently denoted by BKD, whose flow rate at the input of the organization exceeds the fair flow rate implemented by the organization, and the other streams, denoted by NBD (for non-bottlenecked), whose flow rate at the input of the organization is lower than the fair flow rate.
EP 1478140 discloses a mechanism which operates implicit differentiation, that is to say without specific signaling or resource reservation, of the quality of service, by distinguishing between BKD and NBD streams. The packets in NBD streams are handled with priority, while BKD streams undergo fair sharing organization. Thus, “realtime”-type streams (for example audio or video streaming) whose flow rate is relatively low are subject to a slight packet delay. Conversely, “data”-type streams implement the maximum flow rate compatible with a sharing objective.
However, in the mechanism proposed by EP 1478140, NBD streams are momentarily included in the organization's structure when they send a packet. This is necessary in order to allow detection of new BKD streams, but its effect is to necessitate a relatively high capacity for this structure in comparison with that which is strictly necessary for handling BKD streams.
By way of illustration, the organization proposed in the aforementioned techniques can necessitate that several hundred streams be taken into account at certain instants for a served link load of approximately 90%. In reality, the number of streams is dependent on the characteristics of the traffic, particularly on the ratio of the flow rate of the link to the maximum flow rate of the streams (that is to say the flow rate which they would be able to attain if the link had infinite capacity, taking account of the other flow rate limitations on their path). The higher this ratio, for a majority of streams, the greater the number of NBD streams. NBD streams therefore enter the organization's structure more often.
This effect implies the need to use a large memory to identify active streams. Moreover, it implies relatively high processing complexity.
It is also understood that the dependence of the memory necessary for organization on the traffic characteristics means that the dimensioning of the organization's structures is fairly weak.
Furthermore, the fair sharing organization proposed by EP 1478140 provides for identical allocation for all streams. This limitation can be awkward in some applications, particularly in an access network in which it is desirable to distinguish between users according to the conditions provided in their subscription.
It is an object of the present invention to limit the drawbacks of the prior techniques as recalled above.
One particular object of the invention is to limit the information which needs to be taken into account by the organization and the complexity of the processing implemented.
Another object of the invention is to increase the strength of the dimensioning of the organization's structures.
Another object of the invention is to allow special conditions to be taken into account for streams from separate users.